/*
 * @Author: szx
 * @Date: 2022-04-22 14:20:29
 * @LastEditTime: 2022-04-22 14:50:41
 * @Description:
 * @FilePath: \leetcode\剑指offerII\094\094.js
 */
/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
    const n = s.length,
        pre = new Array(n).fill(0).map(() => new Array(n).fill(true));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; ++j) {
            pre[i][j] = s[i] == s[j] && pre[i + 1][j - 1];
        }
    }
    const dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    for (let i = 0; i < n; ++i) {
        if (pre[0][i]) {
            dp[i] = 0;
        } else {
            for (let j = 0; j < i; ++j) {
                if (pre[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    return dp[n - 1];
};
